#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <string.h>

#define MAXPOP 500
#define MAXDIM 500
#define MAXREP 10
#define NUMMAC 50
#define NUMJOB 500
#define MAXWEIGHT 0.9
#define MINWEIGHT 0.4
#define MAXGEN 1000
#define xmax 4.0
#define xmin 0.0
#define vmax 4.0
#define vmin -4.0
#define alpha 10.0
#define lamda 0.00
#define beta 2.0
#define NT 2
#define INFINITY 100000000000.0


typedef int chromosome[NUMJOB];
typedef struct ind{
      chromosome sequence;
      float fitness;
      }individual;

/* Function Prototyping */
float frand();
int vnd1();
int vnd2();
int vnd3();
int repair(individual *child);
int sortarpd();
int sortcpu();
int sortcpu_ebru();
int edd();
int sortedd();
int arpdstd();
int cpustd();
int cpustd_ebru();
int evaluate();
int computeprob();
float urand(float low, float upper);
float readdata();
int randlist(int n,int list[]);
long int rnd(long int low,long int up);
initialize();
/*initpop();*/
initpop(individual *oldpop);
initdata();
float cfitness_tmax(int sequence[],int lbits);
float cfitness_cmax(int sequence[],int lbits);
void initreport();
individual tourselect(int k);
individual tourselect1(int k);
individual tournamentselect(int nt);
int nextpopulation();
int nextpopulation1();
int generation();
int crossover1(individual *child1);
int crossover2(individual *child1);
individual holdbest();
individual bsofar(individual *ptr);
int writebestsofar();
int mutuation1(individual *child2,individual *parent);
int mutation(individual *child2,individual *parent);
int rankoldpop(int ccpop);
int ranknewpop(int ccpop);
int rankpop(int ccpop);
int delpop(int delp);
int delpop1(int delp);
int reorder(int newsequence[]);
int interchange(individual *neighbor,individual *particle,int u,int v);
int insert(individual *neighbor,individual *particle,int u,int v);
int vnd2();
/*Global Variables*/
long int seed;
int ldimension;
float TMAX,SMAX;
int popsize;
int lsequence;
long int gen,cpop,counter,pcount;
long int maxgen=100;
float pcrossover=1.00;
float pmutuation=0.10;
float bmutuation=0.05;
float pimmigration=0.10;

int jcross1,jcross2,jcross3,jcross4,maxcomptime,bestcount;
int cblock[MAXDIM];
int weight[MAXDIM];
int duedate[MAXDIM];
int ptime[NUMJOB][NUMMAC];
int mnum[NUMJOB][NUMMAC];
int tptime[NUMJOB];
int comptime[NUMJOB][NUMMAC];
int row[NUMJOB];
int clength,NUMINSTANCE=160;

float flowtime[MAXDIM];
float lateness[MAXDIM];
float tardiness[MAXDIM];
float wtardiness[MAXDIM];
int maxlateness,maxtardiness;

int noptr,pmcount,tnopti,tnimproved;
int nopti[125];
int nimproved[125];
int wtopt[125];
int njobs,nmach,improved;
int size;
float cmax_fitness,tmax_fitness;
  float rel_per_dev[5000];
  float trpd;
  float avg_rel_per_dev;
  float max_rel_per_dev;

  float cpu_time[5000],cpu_time_ebru[5000];
  float max_cpu_time=100;
  float tcpu_time,tcpu_time_ebru,tdif1,tdif2,tdif2_ebru,stdcpu,stdcpu_ebru,stdarpd;
  float avg_cpu_time,avg_cpu_time_ebru,tot_avg_rel_per_dev;

  char string[150],string1[150],string2[150],spname[20],pname[20],slbound[20],subound[20],scpu1[20],scpu2[20];
  int lbound[125],ubound[125],best[125];
  float ecpu;

individual oldpop[MAXPOP];
individual newpop[MAXPOP];
individual localbest[MAXPOP];
individual pop[MAXPOP];
FILE *fin,*fout,*fres1,*fopt,*fdata,*ftmax,*fstat;

individual globalbest,initbest,bestsofar,bestactual;
individual offspring,offspring1,offspring2,offspring3;

int main(){
  clock_t ticks;
  float newtime,oldtime;
  int i,j,k,ni,nr,ins;


  fout=fopen("initpop1.txt","w");
  fstat=fopen("Stats_OEBRU_BI_GA-PURE_0.00.txt","w");
  fres1=fopen("OEBRU_BI_GA-PURE_0.00.txt","a+");
  ticks=clock();
  pmcount=0;
  trpd=0;
  tnopti=0;
  tot_avg_rel_per_dev=0;
  tdif1=0;
  tdif2=0;
  tdif2_ebru=0;
  tcpu_time=0;
  tcpu_time_ebru=0;

   // readdata();
 fin=fopen("flmax.txt","r");
 for (ins=0;ins<NUMINSTANCE;ins++){
   fgets(string,150 ,fin);
   //printf("%s\n",string);getch();

   fgets(string1,150 ,fin);
   //fscanf(fin,"%s\t %s\n",&spname,&pname);

   //printf("%s\n",string1);getch();
   fscanf(fin,"%s\t %d\n",&slbound,&lbound[ins]);

   //printf("%d\n",lbound[ins]);getch();
   fscanf(fin,"%s\t %d\n",&subound,&ubound[ins]);

   //printf("%d\n",ubound[ins]);getch();
   fscanf(fin,"%s\t %s\t %f\n",&scpu1,&scpu2,&ecpu);

   //printf("%s\t %s\t %.2f\n",scpu1,scpu2,ecpu);getch();
   fgets(string2,150,fin);
   //printf("%s\n",string1);getch();

   fscanf(fin,"%d %d\n",&njobs,&nmach);
   //printf("%d\t %d\t",njobs,nmach);getch();


   for (j=0;j<njobs;j++){
   for (i=0;i<nmach;i++){
      fscanf(fin,"%d\t %d\t",&mnum[j][i],&ptime[j][i]);}
      fscanf(fin,"%d\t",&duedate[j]);}



  /*for (j=0;j<njobs;j++){
   for (i=0;i<nmach;i++){
        printf("%d\t %d\t",mnum[j][i],ptime[j][i]);}
        printf("%d\t",duedate[j]);} getch(); */
  lsequence=njobs;
   /*for (j=0;j<nmach;j++){
          for (i=0;i<njobs;i++){
            fprintf(fdist,"%d %s",ptime[i][j],",");}
            fprintf(fdist,"\n");}*/

 //for (j=0;j<nmach;j++){
   //for (i=0;i<njobs;i++){
     //   printf("%4d",ptime[i][j]);}}getch();



    //maxgen=(3300*log(njobs)+7500*log(nmach)-18500)/njobs;
    //printf("maxgen=%d",maxgen);getch();
    popsize=njobs*2;
    maxgen=500;
    improved=0;
    noptr=0;
    for (nr=0;nr<MAXREP;nr++){
      seed=856765+nr;
      srand(seed);
     if ((ticks=clock())==(clock_t)-1) oldtime=1;
        else oldtime=(float) ticks/CLOCKS_PER_SEC;


    gen=0;
    //bestcount=0;
    initialize();
    initbest.fitness=32670000.0;
    do{
      clrscr();
      printf("replication       =%d\n",nr);
      printf("Generation        =%d\n",gen);
      printf("upperbound        =%d\n",ubound[ins]);
      printf("bestsofar         =%.2f\n",bestsofar.fitness);
      gen++;
      generation();
      //vnd2();
      nextpopulation();
      }while(gen<maxgen);


     /* clrscr();
     printf("bestglobal  fitness  =%.2f\n",globalbest.fitness);
      printf("\n");
      for (i=0;i<ldimension;i++){
        printf("%.2f %s",globalbest.dchrom[i],",");}
        printf("\n");
        printf("\n");
      for (i=0;i<ldimension;i++){
        printf("%.2f %s",globalbest.vchrom[i],",");}
        printf("\n");
        printf("\n");
      for (i=0;i<ldimension;i++){
        printf("%d %s",globalbest.sequence[i],",");}  */
        if ((ticks=clock())==(clock_t)-1) newtime=1;
        else newtime=(float) ticks/CLOCKS_PER_SEC;


      if (bestsofar.fitness<ubound[ins])improved++;
            if (bestsofar.fitness<=ubound[ins])noptr++;

     //rel_per_dev[pmcount]=((bestsofar.fitness-ubound[ins])*100)/ubound[ins];
     //printf("%.2f",rel_per_dev[pmcount]); getch();

     cpu_time[pmcount]=newtime-oldtime;
     cpu_time_ebru[pmcount]=ecpu;

     
     /* printf("ter test");getch();*/
      fprintf(fres1,"%s\n\n",string1);
      fprintf(fres1,"Replication Number j=%d\n",nr);
      fprintf(fres1,"Seed=%d Iteration=%d Popsize=%d ldimension=%d\n",seed,gen,popsize,ldimension);
      fprintf(fres1,"CPU in seconds for PSO =%.2f\n",newtime-oldtime);
      fprintf(fres1,"CPU in seconds for EBRU=%.2f\n",ecpu);
      //fprintf(fres1,"relative percent dev =%.2f\n\n",rel_per_dev[pmcount]);
      //fprintf(fres1,"lower bound          =%d\n",lbound[ins]);
      //fprintf(fres1,"upper bound          =%d\n",ubound[ins]);
      fprintf(fres1,"bestsofar  fitness   =%.2f\n",bestsofar.fitness);
      fprintf(fres1,"\n");

      fprintf(fstat,"%.2f",bestsofar.fitness);
      fprintf(fstat,"\n");
      for (j=0;j<lsequence;j++){
        fprintf(fres1,"%d\t",bestsofar.sequence[j]);}
        fprintf(fres1,"\n");

       pmcount++;


      }fprintf(fres1,"********************************************************************************************\n");
      fprintf(fstat,"%s\n",string1);
      fprintf(fstat,"lamda=%.2f\n",lamda);
      fprintf(fstat,"********************************************************************************************\n");

      if (noptr>0)nopti[ins]=1;
      tnopti+=nopti[ins];
      if (improved>0)nimproved[ins]=1;
      tnimproved+=nimproved[ins];

        //fprintf(fres1,"%.4f\t",trpd/MAXREP);
        //fprintf(fres1,"\n");
        fprintf(fres1,"Problem Number=%d Number of Bestknown Found =%d Number of Improved=%d\t",ins+1,tnopti,tnimproved);
        fprintf(fres1,"\n");
        fprintf(fres1,"********************************************************************************************\n");
      }
      //sortarpd();
      sortcpu();
      cpustd();
      //arpdstd();

      /*fprintf(fres1,"AVG_RPD=%.4f\t",avg_rel_per_dev);
      fprintf(fres1,"\n");
      fprintf(fres1,"MIN_RPD=%.4f\t",rel_per_dev[MAXREP*NUMINSTANCE-1]);
      fprintf(fres1,"\n");
      fprintf(fres1,"MAX_RPD=%.4f\t",rel_per_dev[0]);
      fprintf(fres1,"\n");
      fprintf(fres1,"STD_RPD=%.4f\t",stdarpd);
      fprintf(fres1,"\n");
      fprintf(fres1,"NO=%d\t",tnopti);
      fprintf(fres1,"\n");*/


      fprintf(fres1,"ACPU=%.4f\t",avg_cpu_time);
      fprintf(fres1,"\n");
      fprintf(fres1,"MINCPU=%.4f\t",cpu_time[MAXREP*NUMINSTANCE-1]);
      fprintf(fres1,"\n");
      fprintf(fres1,"MAXCPU=%.4f\t",cpu_time[0]);
      fprintf(fres1,"\n");
      fprintf(fres1,"STDCPU=%.4f\t",stdcpu);
      fprintf(fres1,"\n");

      /*sortcpu_ebru();
      cpustd_ebru();
      fprintf(fres1,"ACPU_EBRU=%.4f\t",avg_cpu_time_ebru);
      fprintf(fres1,"\n");
      fprintf(fres1,"MINCPU_EBRU=%.4f\t",cpu_time_ebru[MAXREP*NUMINSTANCE-1]);
      fprintf(fres1,"\n");
      fprintf(fres1,"MAXCPU_EBRU=%.4f\t",cpu_time_ebru[0]);
      fprintf(fres1,"\n");
      fprintf(fres1,"STDCPU_EBRU=%.4f\t",stdcpu_ebru);
      fprintf(fres1,"\n");*/

      fclose(fin);
      fclose(fres1);
      fclose(fout);
      fclose(fopt);
      fclose(fstat);

return 0;}

int sortarpd(){
    int i,j;
    float temp;
    for (i=0;i<MAXREP*NUMINSTANCE-1;i++)
      for (j=i+1;j<MAXREP*NUMINSTANCE;j++)
        if (rel_per_dev[i]<rel_per_dev[j]){
        temp=rel_per_dev[i];
        rel_per_dev[i]=rel_per_dev[j];
        rel_per_dev[j]=temp;}
  return 0; }

int sortcpu(){
    int i,j;
    float temp;
    for (i=0;i<MAXREP*NUMINSTANCE-1;i++)
      for (j=i+1;j<MAXREP*NUMINSTANCE;j++)
        if (cpu_time[i]<cpu_time[j]){
        temp=cpu_time[i];
        cpu_time[i]=cpu_time[j];
        cpu_time[j]=temp;}
    //printf("cpu=%.4f\n",cpu_time[0]);getch();
return 0; }

int sortcpu_ebru(){
    int i,j;
    float temp;
    for (i=0;i<MAXREP*NUMINSTANCE-1;i++)
      for (j=i+1;j<MAXREP*NUMINSTANCE;j++)
        if (cpu_time_ebru[i]<cpu_time_ebru[j]){
        temp=cpu_time_ebru[i];
        cpu_time_ebru[i]=cpu_time_ebru[j];
        cpu_time_ebru[j]=temp;}
    //printf("cpu=%.4f\n",cpu_time[0]);getch();
return 0; }

int arpdstd(){
int i,j;
    float temp;
    for (i=0;i<MAXREP*NUMINSTANCE;i++){
     tot_avg_rel_per_dev=tot_avg_rel_per_dev+rel_per_dev[i]; }
        avg_rel_per_dev=tot_avg_rel_per_dev/(MAXREP*NUMINSTANCE-1);

    for (i=0;i<MAXREP*NUMINSTANCE;i++){
      tdif1=tdif1+(rel_per_dev[i]-avg_rel_per_dev)*(rel_per_dev[i]-avg_rel_per_dev);}

      stdarpd=sqrt(tdif1/(MAXREP*NUMINSTANCE-2));

return 0; }

int cpustd(){
int i,j;
    float temp;
    for (i=0;i<MAXREP*NUMINSTANCE;i++){
      tcpu_time=tcpu_time+cpu_time[i];}
      avg_cpu_time=tcpu_time/(MAXREP*NUMINSTANCE-1);

    for (i=0;i<MAXREP*NUMINSTANCE;i++){
      tdif2=tdif2+(cpu_time[i]-avg_cpu_time)*(cpu_time[i]-avg_cpu_time);}

      stdcpu=sqrt(tdif2/(MAXREP*NUMINSTANCE-2));

return 0; }

int cpustd_ebru(){
int i,j;
    float temp;
    for (i=0;i<MAXREP*NUMINSTANCE;i++){
      tcpu_time_ebru=tcpu_time_ebru+cpu_time_ebru[i];}
      avg_cpu_time_ebru=tcpu_time_ebru/(MAXREP*NUMINSTANCE-1);

    for (i=0;i<MAXREP*NUMINSTANCE;i++){
      tdif2_ebru=tdif2_ebru+(cpu_time_ebru[i]-avg_cpu_time_ebru)*(cpu_time_ebru[i]-avg_cpu_time_ebru);}

      stdcpu_ebru=sqrt(tdif2_ebru/(MAXREP*NUMINSTANCE-2));

return 0; }





initialize(){
  int i,j;
  initpop(&oldpop[0]);
  for (i=0;i<popsize;i++){
    for (j=0;j<lsequence;j++){
       fprintf(fout,"%d %s",oldpop[i].sequence[j],",");}
       fprintf(fout,"\n");
       fprintf(fout,"\n");}
return 0;}

int initpop(individual *oldpop){
  int i,j,k;

  for (j=0;j<popsize;j++){
      randlist(lsequence,(oldpop+j)->sequence);
      for (i=0;i<lsequence;i++){
          (oldpop+j)->sequence[i]=(oldpop+j)->sequence[i];
          cmax_fitness=cfitness_cmax((oldpop+j)->sequence,ldimension);
          tmax_fitness=cfitness_tmax((oldpop+j)->sequence,ldimension);
          (oldpop+j)->fitness=lamda*cmax_fitness+(1-lamda)*tmax_fitness;}}

          /* printf("\npopulation\n");
           for (j=0;j<popsize;j++){
         for (i=0;i<lsequence;i++){
          printf("%d %s",(oldpop+j)->sequence[i]+1,",");}
          printf("fitness=%.2f cmax=%.2f",(oldpop+j)->fitness,(oldpop+j)->cmax);
          printf("\n");}   getch();   */

    return 0;}



individual holdbest(){
 int i;
 individual b;
 b.fitness=10000000.0;
 for (i=0;i<popsize;i++){
    if (oldpop[i].fitness>b.fitness ){
       b.fitness=oldpop[i].fitness;
       b=oldpop[i];}}
 return b;}

individual bsofar(individual *ptr){
 int i;
 individual bb;
     if (ptr->fitness<initbest.fitness ){
       bestcount=0;
       bb.fitness=ptr->fitness;
       bb=*ptr;
       initbest.fitness=bb.fitness;
       initbest=*ptr;}
   else  {bb=initbest;bestcount++;}
 return bb;}

/*int writebestsofar(){
   int k;
   printf("Penalyzed fitness     =%.2f\n",bestsofar.fitness);
   bestactual=bestsofar;
      bestactual.fitness=cfitness(bestsofar.sequence,lsequence);
      for (k=0;k<lsequence;k++)
           printf("%d %s",bestactual.sequence[k],",");
           printf("bestactual fitness  =%.2f\n",bestactual.fitness);
           if (bestactual.fitness>=SMAX) getch();

   return 0;} */

int randlist(int n, int list[]){
  int i,j;
  float label[NUMJOB];
  float step,u,tu;
  for(i=0;i<n;i++){
     list[i]=-1;
     label[i]=-1;}
  for(i=0;i<n;i++){
     step = 1.0 / ((float)( n-i));
     tu=0.0;
     for(j=0;j<n;j++)
       if ( label[j] ==-1 ){
         u=urand(0.0,1.0);
         tu+=step;
         if ( u <= tu){
           list[i]=j;
           label[j]=1;
           j=n;}}}
   return 0;}

float cfitness_cmax(int seq[],int lbits){
     int i,k,vcount;
     int maxctime;
     float tdist=0.0;
     comptime[seq[0]][0]=ptime[seq[0]][0];
        for (k=1;k<nmach;k++)
          comptime[seq[0]][k]=comptime[seq[0]][k-1]+ptime[seq[0]][k];

        	 for (i=1;i<njobs;i++)
            comptime[seq[i]][0]=comptime[seq[i-1]][0]+ptime[seq[i]][0];

            for (i=1;i<njobs;i++){
              for (k=1;k<nmach;k++){
                comptime[seq[i]][k]=max(comptime[seq[i]][k-1],comptime[seq[i-1]][k])+ptime[seq[i]][k];}}


 maxcomptime=comptime[seq[njobs-1]][nmach-1];
 //printf("\nCmax=%d\n",maxcomptime);getch();
return maxcomptime;}

float cfitness_tmax(int seq[],int lbits){
     int i,k,vcount;
     int maxctime;
     float tdist=0.0;
     comptime[seq[0]][0]=ptime[seq[0]][0];
        for (k=1;k<nmach;k++)
          comptime[seq[0]][k]=comptime[seq[0]][k-1]+ptime[seq[0]][k];

        	 for (i=1;i<njobs;i++)
            comptime[seq[i]][0]=comptime[seq[i-1]][0]+ptime[seq[i]][0];

            for (i=1;i<njobs;i++){
              for (k=1;k<nmach;k++){
                comptime[seq[i]][k]=max(comptime[seq[i]][k-1],comptime[seq[i-1]][k])+ptime[seq[i]][k];}}

       for (i=0;i<njobs;i++){
         lateness[seq[i]]=comptime[seq[i]][nmach-1]-duedate[seq[i]];}

       /*vcount=0;
       for (i=0;i<njobs;i++){
         if (lateness[seq[i]]>vcount){
             maxlateness=lateness[seq[i]];
             vcount=lateness[seq[i]];}} */
       for (i=0;i<njobs;i++){
         tardiness[seq[i]]=max(lateness[seq[i]],0);}
       vcount=0;
       for (i=0;i<njobs;i++){
         if (tardiness[seq[i]]>vcount){
             maxtardiness=tardiness[seq[i]];
             vcount=tardiness[seq[i]];}}


  //printf("\nmax lateness=%d\n",maxtardiness);getch();
return maxtardiness;}

int generation(){
     int i,j,k,loop=0;
     counter=popsize;
     do{
         crossover1(&offspring1);
         cmax_fitness=cfitness_cmax(offspring1.sequence,ldimension);
         tmax_fitness=cfitness_tmax(offspring1.sequence,ldimension);
         offspring1.fitness=lamda*cmax_fitness+(1-lamda)*tmax_fitness;

         oldpop[counter]=offspring1;
         counter++;
         bestsofar=bsofar(&offspring1);
     loop++;
     }while (loop<(int)popsize*pcrossover);
      /*Mutation*/
        for (i=0;i<(int)popsize*pmutuation;i++){
             jcross3=rnd(0,counter-1);
             offspring=oldpop[jcross3];
             mutation(&offspring2,&offspring);
             cmax_fitness=cfitness_cmax(offspring2.sequence,ldimension);
             tmax_fitness=cfitness_tmax(offspring2.sequence,ldimension);
             offspring2.fitness=lamda*cmax_fitness+(1-lamda)*tmax_fitness;

             oldpop[jcross3]=offspring2;
              bestsofar=bsofar(&offspring2);}
return 0;}

int rankoldpop(int ccpop){
    int i,j;
    individual temp;
    for (i=0;i<ccpop-1;i++)
      for (j=i+1;j<ccpop;j++)
        if (oldpop[i].fitness>oldpop[j].fitness){
        temp=oldpop[i];
        oldpop[i]=oldpop[j];
        oldpop[j]=temp;}
  return 0;}

int ranknewpop(int ccpop){
    int i,j;
    individual temp;
    for (i=0;i<ccpop-1;i++)
      for (j=i+1;j<ccpop;j++)
        if (newpop[i].fitness>newpop[j].fitness){
        temp=newpop[i];
        newpop[i]=newpop[j];
        newpop[j]=temp;}
  return 0;}
int rankpop(int ccpop){
    int i,j;
    individual temp;
    for (i=0;i<ccpop-1;i++)
      for (j=i+1;j<ccpop;j++)
        if (pop[i].fitness>pop[j].fitness){
        temp=pop[i];
        pop[i]=pop[j];
        pop[j]=temp;}
  return 0;}

int vnd2(){
int i,j,jj,k,z,m,dloop,kcount,max_method;

 // for (i=0;i<(int)popsize*plocalsearch;i++){
  for (i=0;i<1;i++){

     offspring=bestsofar;

     k=rnd(0,ldimension-1);
     m=rnd(0,ldimension-1);
     insert(&offspring1,&offspring,k,m);

     cmax_fitness=cfitness_cmax(offspring1.sequence,ldimension);
     tmax_fitness=cfitness_tmax(offspring1.sequence,ldimension);
     offspring.fitness=lamda*cmax_fitness+(1-lamda)*tmax_fitness;

     for (z=0;z<ldimension;z++){
                offspring.sequence[z]=offspring1.sequence[z];}

     dloop=0;

    for (k=0;k<ldimension*(ldimension-1);k++){
     m=k+1;
     pcount=0;
     max_method=2;
     kcount=0;
     do{

              //printf("dloop=%d kcount=%d\n",dloop,kcount);getch();
              if (kcount==0) insert(&offspring1,&offspring,k,m);
              if (kcount==1) interchange(&offspring1,&offspring,k,m);
              // getsequence(&offspring1);
               cmax_fitness=cfitness_cmax(offspring1.sequence,ldimension);
               tmax_fitness=cfitness_tmax(offspring1.sequence,ldimension);
               offspring1.fitness=lamda*cmax_fitness+(1-lamda)*tmax_fitness;

              // printf("pop=%.2f\n",offspring1.fitness); getch();
               if (offspring1.fitness<offspring.fitness){
                   offspring.fitness=offspring1.fitness;
                   for (z=0;z<ldimension;z++){
                        offspring.sequence[z]=offspring1.sequence[z];}

                   kcount=0;}
               else{kcount++;}


     }while(kcount<max_method);}
      //printf("dloop=%d kcount=%d\n\n",dloop,kcount);getch();

          if (offspring.fitness<=bestsofar.fitness){
            bestsofar.fitness=offspring.fitness;
           
            for (z=0;z<ldimension;z++){
                bestsofar.sequence[z]=offspring.sequence[z];}}}

return 0;}
int interchange(individual *neighbor,individual *particle,int u,int v){
  int i,j,jcross1,jcross2;
    /* clrscr();
     printf("particle\n");
     for (j=0;j<ldimension;j++){
        printf("%.2f\t",particle->dchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%.2f\t",particle->vchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%d\t",particle->sequence[j]);}
        printf("\n");
        printf("\n");
getch(); */
     u=rnd(0,ldimension-1);
     do{
       v=rnd(0,ldimension-1);
       }while (u==v);
     for (i=0;i<ldimension;i++){
       neighbor->sequence[i]=particle->sequence[i]; }

       neighbor->sequence[u]=particle->sequence[v];
       neighbor->sequence[v]=particle->sequence[u];

         /*     printf("neighbor\n");
     for (j=0;j<ldimension;j++){
        printf("%.2f\t",neighbor->dchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%.2f\t",neighbor->vchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%d\t",neighbor->sequence[j]);}
        printf("\n");
        printf("\n");
getch();*/
return 0;}

int insert(individual *neighbor,individual *particle,int u,int v){
  int i,j,remove,insert;
  float temp1,temp2,temp3;
  for (i=0;i<ldimension;i++){
       neighbor->sequence[i]=particle->sequence[i]; }
   /*  clrscr();
     printf("particle\n");
     for (j=0;j<ldimension;j++){
        printf("%.2f\t",particle->dchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%.2f\t",particle->vchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%d\t",particle->sequence[j]);}
        printf("\n");
        printf("\n");
getch(); */

     remove=rnd(0,ldimension-1);
     do{
       insert=rnd(0,ldimension-1);
       }while (remove==insert);

     // printf("%d\t %d\n",remove,insert);


     temp3=particle->sequence[remove];
     if (remove<insert){
       for (i=remove;i<insert;i++){
          neighbor->sequence[i]=particle->sequence[i+1]; }
          neighbor->sequence[insert]=temp3;}
     else{
         for (i=insert+1;i<=remove;i++){
           neighbor->sequence[i]=particle->sequence[i-1]; }
           neighbor->sequence[insert]=temp3;}


 /*     printf("neighbor\n");
     for (j=0;j<ldimension;j++){
        printf("%.2f\t",neighbor->dchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%.2f\t",neighbor->vchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%d\t",neighbor->sequence[j]);}
        printf("\n");
        printf("\n");
getch();*/

return 0;}

int nextpopulation(){
int i,j,y,z;
  for (y=0;y<popsize;y++){
    newpop[y]=tournamentselect(NT);}
    ranknewpop(popsize);
    newpop[popsize-1]=bestsofar;
    for (y=0;y<counter;y++){
      for (z=0;z<lsequence;z++){
        oldpop[y].sequence[z]=999;}
        oldpop[y].fitness=0.0;}

      for (y=0;y<popsize;y++){
        for (i=0;i<lsequence;i++){
           oldpop[y].sequence[i]=newpop[y].sequence[i];}
           oldpop[y].fitness=newpop[y].fitness;}

return 0;}

int nextpopulation1(){
int i,j,y,z;

    rankoldpop(counter);
    oldpop[popsize-1]=bestsofar;

return 0;}

individual tournamentselect(int nt){
 int i,j,delpoint;
 individual tour;
 tour.fitness=987710000.0;
 for (i=0;i<nt;i++){
    j=rnd(0,counter-1);
    if (oldpop[j].fitness<tour.fitness){
        tour.fitness=oldpop[j].fitness;
        tour=oldpop[j];}}
        //delpoint=j;}}

return tour;}

int delpop(int delp){
int b,a;
  for (b=0;b<counter;b++)
    if (b==delp){
      for (a=0;a<lsequence;a++)
        oldpop[delp].sequence[a]=999;
        oldpop[delp].fitness=0.0;}
        rankoldpop(counter);
        counter--;
return 0;}

individual tourselect(int nt){
 int i,j;
 individual best1;
 best1.fitness=999910000.0;
 for (i=0;i<nt;i++){
    j=rnd(0,popsize-1);
    if (oldpop[j].fitness<best1.fitness){
        best1.fitness=oldpop[j].fitness;
        best1=oldpop[j];}}
   return best1;}

individual tourselect1(int nt){
 int i,j;
 individual best1;
 best1.fitness=10000.0;
 for (i=0;i<nt;i++){
    j=rnd(popsize,counter-1);
    if (oldpop[j].fitness<best1.fitness){
        best1.fitness=oldpop[j].fitness;
        best1=oldpop[j];}}
   return best1;}

int mutation(individual *child2,individual *parent){
  int i;
  jcross1=rnd(0,lsequence-1);
  jcross2=rnd(0,lsequence-1);

  for (i=0;i<lsequence;i++){
       child2->sequence[i]=parent->sequence[i];}

       child2->sequence[jcross1]=parent->sequence[jcross2];
       child2->sequence[jcross2]=parent->sequence[jcross1];
       return 0;}

int crossover1(individual *child1){
    int i,j,k,count,sd,q;
    int pair[NUMJOB],pair1[NUMJOB];

    individual parent1,parent2;
    sd=rnd(0,counter-1);
    parent1=oldpop[sd];
    //parent2=oldpop[sd];
    parent2=tourselect(NT);

    /*clrscr();
    printf("\nBefore Crossover\n");
      for (k=0;k<lsequence;k++)
          printf("%d %s",parent1.sequence[k],",");
          getch();
      printf("\n");
      printf("\n");
      for (k=0;k<lsequence;k++)
          printf("%d %s",parent2.sequence[k],",");
          getch();
     /*crossover*/
      jcross1=rnd(1,(int)lsequence/2);
      jcross2=rnd((int)lsequence/2,lsequence-1);
     /*printf("\njcross1=%d jcross2=%d",jcross1,jcross2);getch();*/
           k=0;
      	  for (i=jcross1;i<jcross2;i++){
               child1->sequence[i]=parent1.sequence[i];
               pair[k]=child1->sequence[i];k++;}

           for (i=0;i<k;i++){
             for (j=0;j<lsequence;j++){
               if (pair[i]==parent2.sequence[j])
                   parent2.sequence[j]=999;}}

          k=0;
          for (i=0;i<lsequence;i++){
            if (parent2.sequence[i]!=999){
            pair1[k]=parent2.sequence[i];k++;}}

            for (i=0;i<jcross1;i++){
                child1->sequence[i]=pair1[i];
                count=i;}
                count++;
           for (i=jcross2;i<lsequence;i++){
                child1->sequence[i]=pair1[count];
                count++;}

      /*printf("\nAfter Crossover\n");
      for (k=0;k<lsequence;k++)
          printf("%d %s",child1->sequence[k],",");
          printf("q=%d",q);
          getch();*/
    return 0;}

/*int crossover2(individual *child1){
    int i,j,k,m,temp,count;
    int pair[5],pair1[5];
    individual parent1,parent2;
    child1->sequence[0]=0;
    parent1=tourselect(NT);
    do{
       parent2=tourselect(NT);
      /* printf("mm\n");
      }while (parent1.fitness==parent2.fitness);

  /*    printf("Before Crossover\n");
      for (k=0;k<lsequence;k++)
          printf("%d %s",parent1.sequence[k],",");
          getch();
      printf("\n");
      for (k=0;k<lsequence;k++)
          printf("%d %s",parent2.sequence[k],",");
          getch();   */
     /*crossover
      jcross1=rnd(1,lsequence-(int)lsequence/2);
      jcross2=rnd(lsequence-(int)lsequence/2,lsequence-1);
     /* printf("\njcross1=%d jcross2=%d",jcross1,jcross2);getch();*
      for (i=0;i<lsequence;i++){
              child1->sequence[i]=0;
              pair1[i]=0;}

           k=0;
      	  for (i=jcross1;i<jcross2;i++){
               child1->sequence[i]=parent1.sequence[i];
               pair[k]=child1->sequence[i];k++;}

           for (i=0;i<k;i++){
             for (j=1;j<lsequence;j++){
               if (pair[i]!=0 && pair[i]==parent2.sequence[j])
                   parent2.sequence[j]=0;}}

          k=0;
          for (i=1;i<lsequence-1;i++){
            if (parent2.sequence[i]!=0){
            pair1[k]=parent2.sequence[i];k++;}}

          if (jcross1>1){
           for (i=1;i<jcross1;i++){
                child1->sequence[i]=pair1[i-1];
                count=i;}
           for (i=jcross2;i<lsequence;i++){
                child1->sequence[i]=pair1[count];
                count++;}}
          else{
              k=0;
              for (i=jcross2;i<lsequence;i++){
                child1->sequence[i]=pair1[k];k++;}}
          child1->sequence[31]=31;

    return 0;}  */

long int rnd(long int low,long int up){
    long int range,result;
    range=up-low+1;
    result=random(range);
    return (result+low);}


float frand(){
     return rand()/(RAND_MAX+1.0); }

float urand(float low, float upper)
{
float u;
u=(float)(low+(upper-low)*( (float) rand()/(float) RAND_MAX) );
if (u==0.000 || u==1.000) u=urand(low,upper);

return u;
}
